package medium;

/**
 * 1026. 节点与其祖先之间的最大差值
 * 创建时间：2024-04-05 11:21
 * 地址：https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/description/
 */
public class 节点与其祖先之间的最大差值_1026 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
        }
   }

    static class Solution {
        public int maxAncestorDiff(TreeNode root) {
            return dfs(root.val, root.val, root);
        }

        private int dfs(int max, int min, TreeNode node) {
            if (node == null) {
                return 0;
            }

            // 先序遍历，先计算根节点与祖先节点的最大差值：max(∣val−min∣,∣val−max∣)
            int ans = Math.max(Math.abs(node.val - min), Math.abs(node.val - max));
            // // min=min(min,val)，max=max⁡(max,val)
            // 更新当前节点与祖先节点的最大最小差值
            max = Math.max(node.val, max);
            min = Math.min(node.val, min);
            // 遍历左右子树
            ans = Math.max(ans, dfs(max, min, node.left));
            ans = Math.max(ans, dfs(max, min, node.right));
            return ans;
        }
    }

}
